//
//  Problem763.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/20.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 763. 划分字母区间
 字符串 S 由小写字母组成。 我们要把这个字符串划分为尽可能多的片段， 同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

 示例：
  输入：S = "ababcbacadefegdehijhklijz"
  输出：[9,7,8]
  解释：
    划分结果为 "ababcbaca", "defegde", "hijhklij"。
    每个字母最多出现在一个片段中。
    像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
 提示：
     S的长度在[1, 500]之间。
     S只包含小写字母 'a' 到 'z' 。
 */
@objcMembers class Problem763: NSObject {
    func solution() {
        print(partitionLabels("ababcbacadefegdehijhklijzyyz"))
    }
    
    /*
     1: 创建一个map，然后遍历字符串，把每个字符的位置存储起来
        a : [1, 3, 6]
        b : [2, 8, 10]
     2: 创建一个起始位置start=0，结束位置end=-1
     3: 再次遍历字符串s，遇到字符c时，找到c在map中的最远位置last，如果这个last > end, 那么end = last
     4: 如果遍历时，正好当前的下标i==end：说明找到了一个字符串，计算他的长度即可。
     */
    func partitionLabels(_ s: String) -> [Int] {
        var map:[Character: [Int]] = [:]
        for (i, c) in s.enumerated() {
            map[c, default: []].append(i)
        }
        
        var result:[Int] = []
        var start = 0
        var end   = -1
        for (i, c) in s.enumerated() {
            if map[c]!.last! > end {
                end = map[c]!.last!
            }
            
            if i == end {
                result.append(end-start+1)
                start = i + 1
                end = -1
            }
        }
        
        return result
    }
}
